package link;

import beans.ListNode;

/**
 * @author pengfei.hpf
 * @date 2020/3/29
 * @verdion 1.0.0
 * 143. 重排链表
 * 给定一个单链表 L：L0→L1→…→Ln-1→Ln ，
 * 将其重新排列后变为： L0→Ln→L1→Ln-1→L2→Ln-2→…
 *
 * 你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
 *
 * 示例 1:
 *
 * 给定链表 1->2->3->4, 重新排列为 1->4->2->3.
 * 示例 2:
 *
 * 给定链表 1->2->3->4->5, 重新排列为 1->5->2->4->3.
 */
public class ReorderList {

    public void reorderList(ListNode head) {
        if(head == null){
            return;
        }
        ListNode slow = head;
        ListNode fast = head;
        while(fast.next != null && fast.next.next != null){
            slow = slow.next;
            fast = fast.next.next;
        }
        if(slow.next != null){
            ListNode newhead = reverse(slow.next);
            slow.next = null;
            merge(head, newhead);
        }
    }

    private ListNode reverse(ListNode node){
        if(node.next == null){
            return node;
        }
        ListNode last = reverse(node.next);
        node.next.next = node;
        node.next = null;
        return last;
    }

    private void merge(ListNode a, ListNode b){
        ListNode dummy = new ListNode(-1);
        ListNode last = dummy;
        while(b != null){
            ListNode tmp = a.next;
            a.next = b;
            last.next = a;
            last = b;
            b = b.next;
            a = tmp;
        }
        if(a != null){
            last.next = a;
        }
    }
}
